/*
Date:20210514 0:19PM
key:对于每长i的绳子，遍历j，j与剩余i-j剪或不剪 就这两种情况的最大。
*/
class Solution 
{
public:
//yy 
    int cuttingRope(int n)
    {
        n++;
        int*dp=new int[n];
        dp[1]=1;
        for(int i=2;i<n;i++)
        {
            int m=0;
            for(int j=1;j<i;j++)
            {
                m=max(m,max(j*dp[i-j],j*(i-j)));
            }
            //cout<<m<<" ";
            dp[i]=m;
        }
        return dp[n-1];
    }
};